#include<iostream>
using namespace std;
struct TreeNode {
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
private:
	int bstToGstCore(TreeNode* root,int more) {
		if (root == NULL) return 0;
		int right = bstToGstCore(root->right, more);
		int left = bstToGstCore(root->left, root->val + more + right);
		int res = root->val + left + right;
		root->val += right + more;
		return res;
	}
public:
	TreeNode* bstToGst(TreeNode* root) {
		bstToGstCore(root,0);
		return root;
	}
};